//
// Created by Administrator on 2021/11/2.
// May Saint Diana bless you!
//
#include <vector>
#include <iostream>
#include <algorithm>


using namespace std;

class Solution {
public:
    int matrixScore(vector<vector<int>> &grid) {
        int m = (int) grid.size(), n = (int) grid[0].size();
        int ans = 0;
        // 首先，每一行的第一个数都应该被置为1，通过翻转这一行来实现
        for (int i = 0; i < m; ++i) {
            if (grid[i][0] == 0) {
                for (int j = 0; j < n; ++j) {
                    grid[i][j] = 1 - grid[i][j];
                }
            }
        }
        ans += m * (1 << (n - 1)); // 每行首个1的贡献
        // 对于第二列及以后，统计该列当前的1和0的个数，如果1多，则不翻转，0多则翻转
        for (int j = 1; j < n; ++j) {
            int OneNum = 0;
            for (int i = 0; i < m; ++i) {
                OneNum += grid[i][j];
            }
            OneNum = max(OneNum, m - OneNum);
            ans += OneNum * (1 << (n - 1 - j));
        }
        return ans;
    }
};

class Solution2 {
public:
    int matrixScore(vector<vector<int>> &grid) {
        int m = grid.size(), n = grid[0].size();
        int ret = m * (1 << (n - 1)); // 每行第一个1的贡献

        for (int j = 1; j < n; j++) {
            int nOnes = 0;
            for (int i = 0; i < m; i++) {
                if (grid[i][0] == 1) { // 可以不需要进行实际的翻转，看这一行的第一个是不是0就行
                    nOnes += grid[i][j];
                } else {
                    nOnes += (1 - grid[i][j]); // 如果这一行进行了行反转，则该元素的实际取值为 1 - grid[i][j]
                }
            }
            int k = max(nOnes, m - nOnes);
            ret += k * (1 << (n - j - 1));
        }
        return ret;
    }
};

int main() {
    vector<vector<int>> grid{{0, 0, 1, 1},
                             {1, 0, 1, 0},
                             {1, 1, 0, 0}};
    Solution solution;
    cout << solution.matrixScore(grid) << endl;
    return 0;
}
